package com.duing.recu;

import java.util.Arrays;

public class ClimbStairs {

    public static void main(String[] args) {
        System.out.println(climbStairsByDP(5));
        System.out.println("=============");
        System.out.println(climbStairsByDP1(5));
    }

    public static int climbStairs(int n) {
        //return climbStairsByRecu(0, n);
        // arr[i]  代表的是起点为i 终点是n 的所有方法
        // arr[0]  arr[1]  arr[2]  arr[3]
        int[] arr = new int[n + 1];
        return climbStairsByRecu(0, n, arr);
    }

    // 递归方法  i起点 n终点
    // 时间O(2^n)  空间O(1)
    public static int climbStairsByRecu(int i, int n) {
        System.out.println("当前的起点和终点为: " + i + "," + n);
        if (i == n) return 1;
        if (i > n) return 0;

        // O(2^(n-1))
        int A = climbStairsByRecu(i + 1, n);
        // O(2^(n-2))
        int B = climbStairsByRecu(i + 2, n);
        int C = A + B;
        System.out.printf("从起点%d到终点%d，方法有%d种", i, n, C);
        System.out.println();
        return C;
    }

    // 记忆化递归
    // 空间O(n)  时间 < O(2^n)
    public static int climbStairsByRecu(int i, int n, int[] arr) {
        System.out.println("当前的起点和终点为: " + i + "," + n + "," +
                Arrays.toString(arr));
        if (i == n) return 1;
        if (i > n) return 0;
        if (arr[i] != 0) {
            return arr[i];
        }

        int A = climbStairsByRecu(i + 1, n, arr);
        int B = climbStairsByRecu(i + 2, n, arr);
        arr[i] = A + B;
        System.out.printf("从起点%d到终点%d，方法有%d种", i, n, arr[i]);
        return arr[i];
    }

    // 动态规划
    // 从已到达终点的角度出发  到达n层的所有方法 dp(n)
    // dp(n) = dp(n-1) + dp(n-2);
    // dp(1) = 1   dp(2) = 2
    // 用迭代来计算  数组来存储  dp从 1...n 的每个值

    // 时间O(n)  空间O(n)
    public static int climbStairsByDP(int n) {
        if (n == 1) return 1;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            System.out.printf("到达 %d 层的所有方法 %d", i, dp[i]);
            System.out.println();
        }
        return dp[n];
    }


    // 用变量存储  而非数组
    // 时间O(n)  空间O(1)
    public static int climbStairsByDP1(int n) {
        if (n == 1) return 1;

        // i2 距离i的值间隔两位的值 dp[i-2]  起始值dp[1]
        int i2 = 1;
        // i1 距离i的值间隔一位的值 dp[i-1]  起始值dp[2]
        int i1 = 2;
        int result = i1;
        for (int i = 3; i <= n; i++) {
            result = i1 + i2;
            // 更新其距离下一个值的 i2和i1
            //  result1 3  i2=2  i1=3
            //  result2 5  i2=3  i1=5
            //  result3 8
            i2 = i1;
            i1 = result;
            System.out.printf("到达 %d 层的所有方法 %d", i, result);
            System.out.println();
        }
        return result;
    }

}
